% Chapter Template

\chapter{Algorithmes de filtrage pour contraintes non binaires} % Main chapter title

\label{Chapter4} % Change X to a consecutive number; for referencing this chapter elsewhere, use \ref{ChapterX}

\lhead{Chapitre 4. \emph{Algorithmes de filtrage pour contraintes non binaires}} % Change X to a consecutive number; this is for the header on each page - perhaps a shortened title

%%----------------------------------------------------------------------------------------
%%	SECTION 1
%%----------------------------------------------------------------------------------------
%\section{Main Section 1}
%
%%-----------------------------------
%%	SUBSECTION 1
%%-----------------------------------
%\subsection{Subsection 1}
%%-----------------------------------
%%	SUBSECTION 2
%%-----------------------------------
%\subsection{Subsection 2}
%
Dans ce chapitre, nous allons présenter les algorithmes pour les consistances de contraintes non binaires. D'abord, nous décrivons le schéma d'un algorithme basé sur GAC-3 pour la propagation de contraintes non binaires et montrons comment cet algorithme peut utilisé pour appliquer RPWC, rPIC and Max-RPWC. Puis, nous abordons deux autres algorithme pour Max-RPWC qui sont plus efficaces que l'autre. Le premier algorithme a une meilleure complexité temporelle mais prend beaucoup d'espace, tandis que le deuxième algorithme équilibre la complexité temporelle et d'espace.

%First we describe the schema of a simple generic AC-3 based algorithm for non-binary domain filtering consistencies, and show how this algorithm can be instantiated to apply RPWC, rPIC, and maxRPWC. Then we describe two alternative algorithms for maxRPWC, which is stronger and, as experimental results show, more cost-effective than RPWC and rPIC. The first of these algorithms has better time complexity than the generic algorithm but worse space complexity, while the second achieves a balance between the other two in terms of time and space complexity. Both these algorithms can be easily modified to apply RPWC and rPIC.


%----------------------------------------------------------------------------------------
\section{Algorithme générique}
%Fig. 2 describes the framework of a generic algorithm for domain filtering consistencies. This is based on coarse-grained GAC algorithms like GAC-3 [18,19] and GAC2001/3.1 [8].

%Algorithm DFcons takes as input a (non-binary) CSP P , a specified domain filtering local consistency DFC and a parameter current-var, and enforces DFC on P . The parameter current-var is set to -1 if the algorithm is used standalone (e.g. for preprocessing a problem with a given consistency). Otherwise if the algorithm is applied during search (e.g. to maintain a given consistency), current-var is the currently assigned variable. 

%DFcons uses a list Q (that can be implemented as a stack or as a queue) of constraints to propagate value deletions, and works as follows. If used stand-alone, the algorithm initially puts all constraints in Q (line 1). Else if the algorithm is applied during search, it calls procedure Enqueue to initialize Q with the appropriate constraints (line 2). These include each constraint cm involving current-var and each constraint intersecting with cm on more than one variable. We now explain why these constraints are added to Q for the case where DFC is rPIC or maxRPWC. A similar explanation holds for RPWC.

Nous décrivons ci-dessous un algorithme générique pour appliquer les consistances : RPWC, rPIC, Max-RPWC. Cet algorithme est basé sur l'algorithme GAC-3. La fonction \textit{DFcons(CSP,DFC, current-var)} prend l'entrée : un CSP non binaire, DFC (le nom de la consistance (RPWC, rPIC, Max-RPWC)) et \textit{current-var}. Le paramètre \textit{current-var} égale -1 quand cet algorithme est utilisé standalone (ex : pour prétraitement le problème avec une consistance donnée). Autrement, si l'algorithme est appliqué pendant la recherche (ex : maintenir une consistance donnée), \textit{current-var} est la variable actuellement assignée. La fonction \textit{DFcons} utilise une liste \textit{Q} de contrainte pour la propagation des valeurs enlevées. Si l'algorithme est utilisé standalone (prétraitement), toutes les contraintes sont mises à \textit{Q} (ligne 2). Si l'algorithme est utilisé pendant la recherche, il appelle $Enqueue(x_j, c_i)$ pour initialiser Q avec les contraintes appropriées (ligne 3). Ces contraintes sont des contraintes $c_m$ portant sur \textit{current-var} et les contraintes intersectées avec $c_m$ sur plus que deux variables.

Ensuite, chaque contrainte $c_i$ dans la liste \textit{Q} est enlevée et examinée. Pour chaque variable $x_j$ appartient à $c_i$, on fait la révision de consistance par la fonction $Revise(x_j, c_i,DFC)$. Cette fonction va parcourir les valeurs dans le domaine de $x_j$ pour enlever les inconsistances. Si le domaine de $x_j$ devient vide, on s'arrête. Autrement, si le domaine de $x_j$ n'est pas vide et quelques valeurs sont enlevées, alors, la fonction $Enqueue(x_j, c_i)$ est appelée pour mettre les contraintes qu'on doit réviser dans \textit{Q}. Si Q est vide, on termine la révision de consistance.

\textbf{Algorithme générique}
\begin{lstlisting}[caption= function DFcons]
function DFcons($CSP,DFC$, current-var)
  if current-var = -1, put all constraints in Q;
  else Enqueue(current-var, -1);
  while Q is not empty
     pop constraint $c_i$ from Q;
     foreach unassigned variable $x_j$ where $x_j \in vars(c_i)$
     if Revise($x_j, c_i,DFC$) $> 0$
        if D($x_j$) is empty return INCONSISTENCY;
        Enqueue($x_j, c_i$);
  return CONSISTENCY;
\end{lstlisting}

%$CSP$: the CSP to filtering domain
%
%$DFC$: the method of filtering (Max-RPWC, RPWC, rPIC)
%
%\textit{current-var}: if algorithm
%\begin{itemize}
%\item is used standalone, \textit{current-var} = -1, put all constraint in Q (line 2)
%\item is applied during search, \textit{current-var} = currently assigned variable,\\ put only constraints associated with \textit{current-var} (line 3)
%\end{itemize}


\begin{lstlisting}[caption= procedure Enqueue]
procedure Enqueue($x_j, c_i$)
   foreach $c_m$ s.t. $x_j \in vars(c_m)$
      put in Q each $c_l(\neq c_i)$ s.t. $|vars(c_l) \cap vars(c_m)| > 1$;
      if $c_m \neq c_i$ put $c_m$ in Q;
\end{lstlisting}

La procédure $Enqueue(x_j, c_i)$ permet à mettre les contraintes à réviser dans la file \textit{Q}. Cette procédure est faite pour les consistances : RPWC, rPIC et MaxRPWC. Quand quelques valeurs de $x_j$ sont supprimées, les contraintes $c_m$ portant sur $x_j$ sont mises dans la file ainsi que les contraintes $c_l$ qui intersectent avec $c_m$ sur plus que une variable doivent être dans la file \textit{Q} car il existe le cas que un tuple $\tau \in rel(c_m)$ est le PW-support du tuple $\tau' \in rel(c_l)$.

Nous décrivons ensuite comment la fonction $Revise(x_j, c_i,DFC)$ est réalisée pour appliquer les consistances RPWC, rPIC et MaxRPWC.

%When some value of $x_j$ is removed, add the constraints $c_m$ ($x_j \in vars(c_m)$) in Q and add other constraints $c_l$ that intersect with $c_m$
%
%	\begin{itemize}
%	\item because a tuple $\tau \in rel(c_m), \tau[x_j]=a$ may be the PW-support of $\tau' \in rel(c_l)$
%	\end{itemize}

%----------------------------------------------------------------------------------------
\section{Max-RPWC-1}
Dans Revise($x_j, c_i,MaxRPWC$), pour chaque valeur $a$ dans $D(x_j)$, on cherche d'abord un tuple $\tau \in rel(c_i)$ qui est GAC-support de $a$. Comme GAC2001/3.1, on sauvegarde le pointer $lastGAC_{x_j, a, c_i}$ pour chaque valeur $a \in D(x_j)$, ce pointeur est backtrackable. C'est le tuple le plus récemment trouvé qui est le GAC-support de $a$ et qui peut s'étendre aux autres contraintes intersectées avec $c_j$. Dans le cas que le tuple $\tau$ n'est plus valide, on considère le tuple suivant de $\tau$ dans l'ordre lexicographique. Si ce nouveau tuple est valide, on examine si ce tuple peut s'étendre aux autres contraintes ou non.

Pour examiner l'expansion d'un tuple, Max-RPWC1 parcourt chaque contrainte $c_m$ intersectée avec $c_j$ sur au moins une variable. L'algorithme examine chaque tuple $\tau' \in rel(c_m)$ pour trouver un valide tuple $\tau'$ qui est PW-support de $\tau$. Si nous pouvons trouver ce tuple dans chaque contrainte $c_m$ pour $\tau$, le nouveau $lastGAC_{x_j, a, c_i}$ est mis à jour (ligne 9) et on considère une autre valeur $a \in D(x_j) $ (ligne 2). S'il n'existe pas de PW-supports pour $\tau$ dans une contrainte $c_m$, alors on doit s'arrêter (ligne 7-8) et recommencer avec un autre tuple dans $c_i$ (ligne 4). Et si aucun GAC-support de $a$ ne peut s'étendre à chacun des contraintes intersectées avec $c_i$, alors $a$ n'est pas Max-RPWC, cette valeur est enlevée (ligne 10). En fin, l'algorithme retourne le nombre de valeur enlevée.\\

\begin{lstlisting}[caption=function Revise of Max-RPWC-1]
function Revise($x_j, c_i,MaxRPWC$)
   for each value $a \in D(x_j)$
      PW $\leftarrow$ FALSE;
      foreach valid $\tau (\in rel(c_i)) \geq_l lastGAC_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
         PW $\leftarrow$ TRUE;
         for each $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
            if $\nexists$ valid $\tau' (\in rel(c_m))$ s.t. $\tau[vars(c_i) \cap vars(c_m)] = \tau' [vars(c_i) \cap vars(c_m)]$
               PW $\leftarrow$ FALSE; break;
         if PW = TRUE $lastGAC_{x_j,a,c_i} \leftarrow \tau$; break;
      if PW = FALSE remove $a$ from $D(x_j)$;
   return number of deleted values;
\end{lstlisting}

%Line 4-10: for each valid tuple $\tau \in rel(c_m), \tau[x_j]=a$, check if it can be extended to each constraint intersecting with $c_m$. If not, remove $a$ from $D(x_j)$.\\
%Line 6-7: for each constraint $c_m$, check if $\tau$ has PW-support $\tau'$ in $c_m$.

%\begin{itemize}
%\item Time complexity: $O(e^2k^2d^p)$, $p$ is the maximum number of variables involved in two constraints sharing at least two variables.
%\item Space complexity: $O(ekd)$
%\end{itemize}

Cet algorithme a une complexité temporelle de $O(e^2k^2d^p)$ et une complexité d'espace en $O(ekd)$ où $p$ est le nombre maximum de variables impliquées dans deux contraintes. La démonstration est présentée dans \cite{bessiere2008domain}.

%----------------------------------------------------------------------------------------
\section{rPIC-1}

Dans Revise($x_j,c_i,rPIC$), pour chaque valeur $a \in D(x_j)$, on parcourt chaque contrainte $c_m$ intersectée avec $c_i$ sur au moins deux variable. L'algorithme cherche un tuple $\tau \in rel(c_i)$ qui peut s'étendre à la contrainte $c_m$. Un pointeur $lastGAC_{x_j,a,c_i,c_m}$ est utilisé pour chaque contrainte $c_m$ intersectée avec $c_i$, ce pointeur est backtrackable. C'est le tuple le plus récemment trouvé dans $rel(c_i)$ qui est GAC-support de $a \in D(x_j)$ et peut s'étendre à la contrainte $c_m$. Si ce tuple est valide, alors $a$ est rPIC. Si non, on cherche un nouveau GAC-support pour $a$ à partir de $lastGAC_{x_j,a,c_i,c_m}$ (ligne 5). Si le nouveau GAC-support $\tau$ est trouvé et ce tuple est valide, l'algorithme examine si ce tuple peut s'étendre à $c_m$ par chercher le PW-support $\tau'$ de $\tau$ (ligne 6). Si $\tau'$ est trouvé, $lastGAC_{x_j,a,c_i,c_m}$ est mis à jour (ligne 7). Si $\tau'$ n'est pas trouvé, alors on recommence à ligne 5. Dans le cas où il n'y a plus de GAC-support pour $a$ in $rel(c_m)$, alors on doit enlever $a$. Enfin, l'algorithme retourne le nombre de valeur enlevée.\\


\begin{lstlisting}[caption= function Revise of rPIC-1]
function Revise($x_j,c_i,rPIC$)
   foreach value $a \in D(x_j)$
      foreach $c_m$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
         PW $\leftarrow$ FALSE;
         foreach valid $\tau (\in rel(c_i)) \geq_l lastGAC_{x_j,a,c_i,c_m}$ s.t. $\tau[x_j] = a$
            if $\exists$ valid $\tau' (\in rel(c_m))$ s.t. $\tau[vars(c_i) \cap vars(c_m)] = \tau'[vars(c_i) \cap vars(c_m)]$
               $lastGAC_{x_j,a,c_i,c_m} \leftarrow \tau$;
               PW $\leftarrow$ TRUE; break;
         if PW = FALSE remove $a$ from $D(x_j)$; break;
   return number of deleted values;
\end{lstlisting}

%Line 2-9: for each $a \in D(x_j)$, for each pair of intersecting constraints $(c_i, c_m)$, check if exist a pair of tuples $\tau \in rel(c_i), \tau' \in rel(c_m),$ s.t. $\tau'$ is PW-support for $\tau$. If not, remove $a$ from $D(x_j)$

%\begin{itemize}
%\item Time complexity: $O(e^2k^2d^p)$
%\item Space complexity: $O(e^2kd)$
%\end{itemize}

Cet algorithme a une complexité temporelle de $O(e^2k^2d^p)$ et une complexité d'espace en $O(e^2kd)$ où $p$ est le nombre maximum de variables impliquées dans deux contraintes \cite{bessiere2008domain}.

%----------------------------------------------------------------------------------------
\section{RPWC-1}

Nous présentons dans cette partie un algorithme pour RPWC. L'idée est comme suit. A chaque appel à \textit{Revise($x_j,c_i,RPWC$)}, on cherche deux GAC-support pour chaque valeur $a\in D(x_j)$. Si on trouve un seul GAC-support pour $a$, alors, on doit examiner si ce GAC-support peut s'étendre aux autres contraintes intersectées avec $c_i$. Deux pointeur $lastGAC1_{x_j,a,c_i}$, $lastGAC2_{x_j,a,c_i}$ sont utilisés, ces pointeurs sont backtrackable. $lastGAC1_{x_j,a,c_i}$, $lastGAC2_{x_j,a,c_i}$ sont deux GAC-supports les plus récemment trouvés pour $a$. Si $lastGAC2_{x_j,a,c_i} = NIL$, c'est-à-dire que tous les possibles GAC-support pour $a$ sont considérés. Si $lastGAC2_{x_j,a,c_i}$ n'est pas ni valide ni \textit{NIL}, on cherche un nouveau GAC-support après $lastGAC2_{x_j,a,c_i}$ (ligne 3-4). Si un GAC-support est trouvé, $lastGAC2_{x_j,a,c_i}$ est mis à jour. Si non, c'est à dire que tous les tuples sont examinés et on met $lastGAC2_{x_j,a,c_i} = NIL$ (ligne 5-6). Ensuite, si $lastGAC1_{x_j,a,c_i}$ n'est plus valide, alors, on doit mettre $lastGAC1_{x_j,a,c_i} = lastGAC2_{x_j,a,c_i}$ et cherche un nouveau GAC-support pour $lastGAC2_{x_j,a,c_i}$. Si on ne trouve pas de nouveau GAC-support, alors $lastGAC1_{x_j,a,c_i} = NIL$ (ligne 7-11). Ce processus assure que $lastGAC1_{x_j,a,c_i}$, $lastGAC2_{x_j,a,c_i}$ sont deux GAC-supports les plus récemment trouvés ou $\forall \tau : lastGAC1_{x_j,a,c_i} <_l lastGAC2_{x_j,a,c_i}$ et $\forall \tau : lastGAC1_{x_j,a,c_i} <_l \tau <_l lastGAC2_{x_j,a,c_i}$, $\tau$ est invalide ou $\tau[x_j] \neq a.$\\

\begin{lstlisting}[caption=function Revise of RPWC-1]
function Revise($x_j,c_i,RPWC$)
   foreach value $a \in D(x_j)$
      if $lastGAC2_{x_j,a,c_i} \neq NIL$ and $lastGAC2_{x_j,a,c_i}$ is not valid
         if $\exists$ valid $\tau (\in rel(c_i)) \geq_l lastGAC2_{x_j,a,c_i}$ s.t. $\tau [x_j] = a$
            $lastGAC2_{x_j,a,c_i} \leftarrow \tau$;
         else $lastGAC2_{x_j,a,c_i} \leftarrow NIL$;
      if $lastGAC2_{x_j,a,c_i} \neq NIL$ and $lastGAC1_{x_j,a,c_i}$ is not valid
         $lastGAC1_{x_j,a,c_i} \leftarrow lastGAC2_{x_j,a,c_i}$;
         if $\exists$ valid $\tau (\in rel(c_i)) \geq_l lastGAC2_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
            $lastGAC2_{x_j,a,c_i} \leftarrow \tau$;
         else $lastGAC2_{x_j,a,c_i} \leftarrow NIL$;
      if $lastGAC1_{x_j,a,c_i}$ is not valid $PW \leftarrow FALSE$;
      else if $lastGAC2_{x_j,a,c_i} = NIL$
         PW $\leftarrow$ FindPWsupports($c_i,lastGAC1_{x_j,a,c_i}$);
      else PW = TRUE;
      if PW = FALSE remove a from $D(x_j)$;
   return number of deleted values;
\end{lstlisting}

Puis, si $lastGAC1_{x_j,a,c_i} = NIL$, c'est à dire qu'il n'y a pas de GAC-support pour $a$, on doit donc enlever $a$ (ligne 12 et 16). Autrement, si $lastGAC2_{x_j,a,c_i} = NIL$, c'est à dire qu'il y a un seul GAC-support pour $a$, alors la fonction \textit{FindPWsupports($c_i,\tau$)} est appelée pour tester si ce tuple peut s'étendre aux autres contraintes intersectées avec $c_i$. D'autre cas, si $lastGAC2_{x_j,a,c_i} \neq NIL$, c'est à dire qu'il y a au moins deux GAC-supports pour $a$ et $a$ est RPWC. Enfin, l'algorithme retourne le nombre de valeur enlevée.
%Line 2-14: for each $a \in D(x_j)$, check if it has unique GAC-supports in $c_i$. If true, find PW-support of this GAC-support in each constraint intersecting with $c_i$ (line 14).

La fonction FindPWsupports($c_i,\tau$) permet à tester l'extension d'un tuple $\tau \in rel(c_i)$. Pour chaque contrainte $c_m$ intersectée avec $c_i$, on cherche un PW-support $\tau' \in rel(c_m)$ pour $\tau$. Si dans une $c_m$, le PW-support n'est pas trouvé, alors $\tau$ n'est pas extensible, on s'arrête et retourne \textit{FASLE}. Sinon, $\tau$ est extensible, on retourne \textit{TRUE}.\\

\begin{lstlisting}[caption=function FindPWsupports of RPWC-1]
function FindPWsupports($c_i,\tau$)
   PW $\leftarrow$ TRUE;
   foreach $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
      if $\nexists$ valid $\tau' (\in rel(c_m))$ s.t. $\tau[vars(c_i ) \cap vars(c_m)] = \tau'[vars(c_i) \cap vars(c_m)]$
         PW $\leftarrow$ FALSE; break;
   return PW;
\end{lstlisting}

%Line 3-5: check if a tuple $\tau \in rel(c_i)$ has PW-support in each constraint intersecting with $c_i$.

%\begin{itemize}
%\item Time complexity: $O(ne^2k^2d^k)$
%\item Space complexity: $O(ekd)$
%\end{itemize}

Cet algorithme a une complexité temporelle de $O(ne^2k^2d^p)$ et une complexité d'espace en $O(ekd)$ où $p$ est le nombre maximum de variables impliquées dans deux contraintes \cite{bessiere2008domain}.


%----------------------------------------------------------------------------------------
\section{Max-RPWC-2}

Nous abordons dans cette section un autre algorithme pour Max-RPWC qui a une meilleure complexité temporelle mais la complexité d'espace est grande. Cet algorithme est une amélioration de MaxRPWC-1. Dans MaxRPWC-1, à chaque fois on trouve un nouveau tuple $\tau$, le temps de tester si $\tau$ peut s'étendre aux autres contraintes intersectées avec $c_i$ coûte chère. Supposant que l'intersection est sur $f$ variables, pour chaque itération, l'algorithme peut vérifier tous $d^{k-f}$ sous tuple qui incluent l'assignation $\tau[vars(c_i) \cap vars(c_m)]$. Ce processus peut répéter à chaque révision de $c_i$. Pour régler ce problème, pour chaque contrainte $c_i$, Max-RPWC-2 tient un ensemble de $d^f$ pointeurs pour chaque contrainte $c_m$ intersectée avec $c_i$. Chaque pointeur $lastPW_{c_i,c_m,s}$ correspond au sous tuple $s$ entre $d^f$ sous tuples pour les variables $vars(c_i) \cap vars(c_m)$. Pendant l'exécution de l'algorithme, $lastPW_{c_i,c_m,s}$ indique le tuple valide le plus récemment trouvé qui étend le sous-tuple $s$, ce pointeur es backtrackable.

Pour chaque révision, pour chaque valeur $a \in D(x_j)$ on cherche un tuple $\tau \in rel(c_i)$ qui est valide et GAC-support de $a$, cette étape est la même avec Max-RPWC-1 (ligne 2-5). Pour chaque contrainte $c_m$ intersectée avec $c_i$, Max-RPWC-2 vérifie si tous les extensions possibles de $s$ ($s = \tau[vars(c_i) \cap vars(c_m)]$) dans $c_m$ ont été examinées avant. Si $lastPW_{c_i,c_m,s} = NIL$, c'est à dire que $s$ n'a plus d'extension dans $c_m$ et on doit terminer et recommencer par un autre GAC-support pour $a$ (ligne 14). Autrement, si $lastPW_{c_i,c_m,s} \neq NIL$, l'algorithme cherche une extension pour $s$ à partir de $lastPW_{c_i,c_m,s}$ par l'ordre lexicographique (ligne 9). Si un tuple $\tau'$ est trouvé, $lastPW_{c_i,c_m,s}$ est mis à jour (ligne 10). Autrement, $lastPW_{c_i,c_m,s}$ est mis à $NIL$ (ligne 12). Dans le cas, il n'y a pas de GAC-support pour $a$ qui peut s'étendre aux contraintes $c_m$ intersectées avec $c_i$, $a$ est supprimé. Enfin, l'algorithme retourne le nombre de valeur enlevée.\\

\begin{lstlisting}[caption= function Revise of Max-RPWC-2]
function Revise($x_j,c_i, MaxRPWC$)
   foreach value $a \in D(x_j)$
      PW $\leftarrow$ FALSE;
      foreach valid $\tau (\in rel(c_i )) \geq_l lastGAC_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
         PW $\leftarrow$ TRUE;
         foreach $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
            $s \leftarrow \tau[vars(c_i) \cap vars(c_m)]$;
            if $lastPW_{c_i,c_m,s} \neq NIL$
               if $\exists$ valid $\tau' (\in rel(c_m )) \geq_l lastPW_{c_i,c_m,s}$ and $\tau'[vars(c_i) \cap vars(c_m)] = s$
                  $lastPW_{c_i,c_m,s} \leftarrow \tau'$;
               else
                  $lastPW_{c_i,c_m,s} \leftarrow NIL$;
                  PW $\leftarrow$ FALSE; break;
            else PW $\leftarrow$ FALSE; break;
         if PW = TRUE, $lastGAC_{x_j,a,c_i} \leftarrow \tau$; break;
      if PW = FALSE, remove $a$ from $D(x_j)$;
   return number of deleted values;
\end{lstlisting}

\begin{figure}[ht]
	\centering
	\includegraphics[height=3cm]{./images/non-binary/MaxRPWC2_MaxRPWC1.png}
	\caption{Applique Max-RPWC-1 et Max-RPWC-2 sur un CSP non-binaire}
	\label{fig:MaxRPWC2_MaxRPWC1}
\end{figure}

\begin{example}
Etant donné un CSP dans la figure~\ref{fig:MaxRPWC2_MaxRPWC1}, $X = \{x_1, x_2, x_3, x_4\}$ et $C = \{c_1, c_2\}$, les contraintes $c_1, c_2$ intersectent sur deux variables $x_1, x_2$. Les tuples en gras sont autorisés par les contraintes et sont valides. Les tuples en italique ne sont pas autorisés par les contraintes. Supposant que on doit tester si les valeurs de $x_1$ sont Max-RPWC. Max-RPWC-1 doit examiner tous les 5 tuples de $c_2$ pour chaque valeur de $x_1$. Max-RPWC-2 examine 5 tuples seulement pour la valeur 0 de $x_1$ car après avoir examiné $x_1 = 0$, $lastPW_{c_i,c_m,s}$ ($s = \{0, 0\}$) indique le tuple $\{0, 0, 4\}$ dans $c_2$. Pour les autres valeurs de $x_1$,  Max-RPWC-2 vérifie seulement ce tuple.

\end{example}

%For each constraint $c_i$, Max-RPWC-2 keeps a set of $d^f$ pointers \{$lastPW_{c_i,c_m,s}$\} for every constraint $c_m$ intersecting with $c_i$. 
%\begin{itemize}
%\item Time complexity: $O(e^2k^2d^k)$
%\item Space complexity: $O(ekd^f)$, where $f$ is the maximum number of intersecting variables on two constraints
%\end{itemize}
%
%\textbf{Max-RPWC-2} is not practical when the number of sharing variables is large.

Max-RPWC-2 une complexité temporelle de $O(e^2k^2d^k)$ et une complexité d'espace en $O(ekd^f)$, où $f$ est le nombre maximum de variable intersectée dans deux contraintes \cite{bessiere2008domain}. Cet algorithme a une bonne complexité temporelle en comparaison avec GAC2001/3.1 ($O(ek^2d^k)$) mais il prend d'espace. Il n'est pas pratique dans le cas où le nombre variable intersectée dans deux contraintes est grand.

%----------------------------------------------------------------------------------------
\section{Max-RPWC-3}
Max-RPWC-2 a une bonne complexité temporelle par rapport à Max-RPWC-1 mais si le problème est grand, on doit utiliser beaucoup de mémoire. Dans cette section, nous abordons le troisième algorithme pour Max-RPWC, l'algorithme Max-RPWC-3, cet algorithme économise quelque teste de l'extension par rapport à Max-RPWC-1 et il a besoin moins de mémoire que Max-RPWC-2.

En plus du pointeur $lastGAC_{x_j,a,c_i}$, Max-RPWC-3 utilise un autre pointeur $lastPW_{x_j,a,c_i,c_m}$ pour chaque contrainte $c_m$ intersectée avec $c_i$, et pour chaque $a\in D(x_j)$. Ce pointeur est le plus récemment PW-support pour $lastGAC_{x_j,a,c_i}$ dans $rel(c_m)$.

Max-RPWC-3 va d'abord chercher un GAC-support pour $a$ comme Max-RPWC-1 (ligne 2-4). Si $lastGAC_{x_j,a,c_i}$ est encore valide, Max-RPWC-3 examine la validité des PW-support $lastPW_{x_j,a,c_i,c_m}$ pour les contraintes $c_m$ intersectées avec $c_i$. Si pour quelques contraintes $c_m$, $lastPW_{x_j,a,c_i,c_m}$ n'est plus valide, Max-RPWC-3 cherche un autre PW-support pour $lastGAC_{x_j,a,c_i}$ à partir de $lastPW_{x_j,a,c_i,c_m}$. De cette façon, Max-RPWC-3 économise quelques testes d'extension. Si $lastGAC_{x_j,a,c_i}$ n'est plus valide, l'algorithme cherche un autre GAC-support pour $a$ et puis il examine si ce tuple peut s'étendre aux autres contraintes comme Max-RPWC-1. S'il n'y pas de GAC-support pour $a$ qui peut s'étendre aux contraintes $c_m$, l'algorithme enlève $a$. Enfin, le nombre de valeur enlevé est retourné.\\

\begin{lstlisting}[caption= function Revise of Max-RPWC-3]
function Revise($x_j,c_i,MaxRPWC$)
   foreach value $a \in D(x_j)$
      PW $\leftarrow$ FALSE;
      foreach valid $\tau (\in rel(c_i)) \geq_l lastGAC_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
         PW $\leftarrow$ TRUE;
         foreach $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
            if $\tau = lastGAC_{x_j,a,c_i}$, $t \leftarrow lastPW_{x_j,a,c_i,c_m}$;
            else $t \leftarrow$ first tuple in $rel(c_m)$;
            if $\nexists$ valid $\tau'(\in rel(c_m)) \geq_l t$ s.t. $\tau[vars(c_i) \cap vars(c_m)] = \tau'[vars(c_i) \cap vars(c_m)]$
               PW $\leftarrow$ FALSE; break;
            else $lastPW_{x_j,a,c_i,c_m} \leftarrow \tau'$;
         if PW = TRUE, $lastGAC_{x_j,a,c_i} \leftarrow \tau$; break;
      if PW = FALSE, remove $a$ from $D(x_j)$;
   return number of deleted values;
\end{lstlisting}

%Max-RPWC stores a pointer $lastPW_{x_j,a,c_i,c_m}$ for each pair of intersecting constraints $c_i,c_m$

%\textbf{Max-RPWC-3}
%\begin{itemize}
%\item Time complexity: $O(e^2k^2d^p)$ but in practice Max-RPWC-3 is better than Max-RPWC-1
%\item Space complexity: $O(e^2kd)$
%\end{itemize}

Cet algorithme a une complexité temporelle de $O(e^2k^2d^p)$ et une complexité d'espace en $O(e^2kd)$ où $p$ est le nombre maximum de variables impliquées dans deux contraintes \cite{bessiere2008domain}. Max-RPWC3 a une même complexité temporelle avec Max-RPWC1 mais dans en pratique, il sera plus efficace parce que dans le cas que le PW-support $\tau'$ de $\tau$ est enlevé, il commence par le tuple suivant  de $\tau'$.



%----------------------------------------------------------------------------------------
\section{Résumé}
	\begin{table}[h]
	\centering
	\begin{tabular}{ | l | l | l |}
	\hline
	\textbf{Algorithme} & \textbf{Complexité de temps} & \textbf{Complexité d'espace} \\ 
	\hline
	GAC3.1/2001 & $O(ek^2d^k)$ & $O(ekd)$ \\ 
	\hline
	RPWC-1 & $O(e^2k^2d^p)$ & $O(ekd)$ \\ 
	\hline
	rPIC-1 & $O(e^2k^2d^p)$ & $O(e^2kd)$ \\ 
	\hline
	MaxRPWC-1 & $O(e^2k^2d^p)$ & $O(ekd)$ \\
	\hline
	MaxRPWC-2 & $O(e^2k^2d^k)$ & $O(ekd^f)$ \\
	\hline
	MaxRPWC-3 & $O(e^2k^2d^p)$ & $O(e^2kd)$ \\
	\hline
	\end{tabular}
	\caption{Résumé des algorithmes avec leur complexité de temps et d'espace}
	\end{table}
 
   	Dans ce chapitre, nous avons abordé les algorithmes pour les consistances RPWC, rPIC, Max-RPWC. Trois algorithmes sont proposés pour Max-RPWC : Max-RPWC-1, Max-RPWC-2, Max-RPWC-3. Entre les algorithmes pour Max-RPWC, l'algorithme Max-RPWC-2 a une bonne complexité temporelle mais il a besoin de mémoire. L'algorithme Max-RPWC-3 a un compromis entre les deux. La table ci-dessous donne la résumé des algorithmes étudiés avec leur complexité temporelle et d'espace.

%----------------------------------------------------------------------------------------
